package Algorithm.Greedy;

import java.util.ArrayList;
import java.util.List;

public class Code07_InsertInterval {

    public static class Interval{
        int start;
        int end;

        Interval(int s, int e){
            start = s;
            end = e;
        }
    }

    // items中，区间从小到大出现的，无重复区域
    public static List<Interval> insert(List<Interval> items, Interval newItem) {
        List<Interval> result = new ArrayList<>();
        int index = 0;
        // 左侧不会被影响到的区间，原封不动放入结果序列中
        while (index < items.size() && items.get(index).end > newItem.start){
            result.add(items.get(index++));
        }
        // 覆盖情况
        while (index <items.size() && items.get(index).start <= newItem.end){
            newItem.start = Math.min(newItem.start, items.get(index).start);
            newItem.end = Math.max(newItem.end, items.get(index).end);
            index ++;
        }
        result.add(newItem);
        while (index <items.size()){
            result.add(items.get(index++));
        }
        return result;
    }

    public static void main(String[] args){
        List<Interval> items = new ArrayList<>();
        items.add(new Interval(1,5));
        items.add(new Interval(6,9));
        items.add(new Interval(13,17));
        Interval newItem = new Interval(7,14);
        List<Interval> res = insert(items, newItem);
        int index = 0;
        while (index < res.size()) {
            System.out.println("[" + res.get(index).start + "," + res.get(index).end + "]");
            index++;
        }
    }
}
